<?php 
/** 
 * 两个链表的第一个公共结点
 * 方法一：
 * 		将两个两边各自压入栈中，然后出栈，待到不相同的节点，前一个节点为公共节点，时间空间复杂度为O(m+n)
 * 方法二：
 * 		先将两个节点遍历，取各自长度，然后求长的长度减去短的长度的值作为offser，然后长的先走offset步，然后两个节点一起遍历，直到找到相同的公共节点，不需要辅助空间，时间复杂度为O(m+n)
 */

class ListNode{
    public $val;
    public $next = NULL;
    public function __construct($x){
        $this->val = $x;
    }
}


function FindFirstCommonNode1($pHead1, $pHead2)
{
	if ($pHead1 == null) 
		return null;
	if ($pHead2 == null) 
		return null;

    $stack1 = [];
    $stack2 = [];

    while ($pHead1 != null) {
 		array_push($stack1, $pHead1);
 		$pHead1 = $pHead1->next;
    }
    while ($pHead2 != null) {
 		array_push($stack2, $pHead2);
 		$pHead2 = $pHead2->next;
    }
    $com_node = null;
    while (!empty($stack1) && !empty($stack2)) {
    	$node1 = array_pop($stack1);
    	$node2 = array_pop($stack2);
        if ($node1 == $node2) {
        	$com_node = $node1;
        } else {
        	break;
        }
    }
    return $com_node;
}


function FindFirstCommonNode2($pHead1, $pHead2)
{
    if ($pHead1 == null) 
		return null;
	if ($pHead2 == null) 
		return null;
	$head1_length = getListLength($pHead1);
	$head2_length = getListLength($pHead2);

	$headLong = $pHead1;
	$headShort = $pHead2;
	$headOffset = $head1_length - $head2_length;

	if ($head1_length < $head2_length) {
		$headLong = $pHead2;
		$headShort = $head1;
		$headOffset = $head2_length - $head1_length;
	}
   
   	for ($i = 0; $i < $headOffset ; $i++) { 
   		$headLong = $headLong->next;
   	}

   	while ($headLong != null && ($headShort != null) && ($headLong != $headShort)) {
   		$headLong = $headLong->next;
   		$headShort = $headShort->next;
   	}
   	$com_node = $headLong;
   	return $com_node;

}

function getListLength($head)
{
	$length = 0;
	$cur_node = $head;
	while ($cur_node != null) {
		$length++;
		$cur_node = $cur_node->next;
	}
	return $length;
}



$com_node = new ListNode(7);
$com_node->next = new ListNode(8);
$com_node->next->next = new ListNode(9);

$head1 = new ListNode(1);
$head1->next = new ListNode(2);
$head1->next->next = new ListNode(3);
$head1->next->next->next = $com_node;

$head2 = new ListNode(4);
$head2->next = new ListNode(5);
$head2->next->next = new ListNode(6);
$head2->next->next->next = $com_node;

var_dump(FindFirstCommonNode2($head1, $head2));

